#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/08/24
# @Author   :Changshu
# @File     :practice_100.py
# 100. 相同的树 给定两个二叉树，编写一个函数来检验它们是否相同。
import collections


class TreeNode:
	def __init__(self,val=0,left=None,right=None):
		self.val=val
		self.left=left
		self.right=right

def isSameTree(p:TreeNode,q:TreeNode)->bool:

	queue1=deque([p])
	queue2=deque([q])

	while len(queue1)!=0 or len(queue2)!=0:
		pt=queue1.popleft()
		qt=queue2.popleft()
		if pt==None and qt==None:
			continue
		elif pt==None or qt==None:
			return False
		if pt.val != qt.val:
			return False
		queue1.append(pt.left)
		queue1.append(pt.right)

		queue2.append(qt.left)
		queue2.append(qt.right)

	return True


def isSameTree2( p: TreeNode, q: TreeNode) -> bool:
	if not p and not q:
		return True
	if not p or not q:
		return False
	deque1 = collections.deque([p])
	deque2 = collections.deque([q])
	while deque1 and deque2:
		node1 = deque1.popleft()
		node2 = deque2.popleft()
		if node1.val != node2.val:
			return False
		left1, right1 = node1.left, node1.right
		left2, right2 = node2.left, node2.right
		if not left1 and left2:
			return False
		if left1 and not left2:
			return False
		if not right1 and right2:
			return False
		if right1 and not right2:
			return False
		deque1.append(left1)
		deque2.append(left2)
		deque1.append(right1)
		deque2.append(right2)
	return not deque1 and not deque2




if __name__ == '__main__':
	''''''
	p=TreeNode(1,None,None)
	p1=TreeNode(2,None,None)
	p2=TreeNode(3,None,None)
	p.left=p1
	p.right=p2

	q=TreeNode(1,None,None)
	q1 = TreeNode(2, None, None)
	q2 = TreeNode(3, None, None)
	q.left=q1
	q.right=q2

	print(isSameTree2(p,q))


	'''
	node1=TreeNode(1,None,None)
	node2=TreeNode(2,None,None)
	node3=None
	# print((not node1)^(not node2))

	# print(1^2)

	print(node1 is None)
	print(not node1)
	print(node1 and node3)
	'''